package week_7.homework;

public class AVLTree<T extends Comparable<T>> {
    private AVLNode<T> root;

    private int h(AVLNode<T>  x) {
        if(x==null)
            return 0;
        else
            return x.height;
    }
    //左旋
    private AVLNode<T> L(AVLNode<T> x) {
        AVLNode<T> mid=x.left;
        x.left=mid.right;
        mid.right=x;
        x.height=Math.max(h(x.left),h(x.right))+1;
        mid.height=Math.max(mid.left.height,x.height)+1;
        return mid;
    }
    //右旋
    private AVLNode<T> R(AVLNode<T> x){
        AVLNode<T> mid=x.right;
        x.right = mid.left;
        mid.left = x;
        x.height = Math.max(h(x.left),h(x.right))+1;
        mid.height = Math.max(mid.right.height,x.height)+1;
        return mid;
    }
    //左右旋
    private AVLNode<T> LR(AVLNode<T> x) {
        x.left=R(x.left);
        return L(x);
    }
    //右左旋
    private AVLNode<T> RL(AVLNode<T> x){
        x.right=L(x.right);
        return R(x);
    }
    //添加
    public void add(T value) {
        if (value==null){
            throw new RuntimeException("data can\'t not be null ");
        }
        this.root=insert(value,root);
    }
    //添加到树中
    private AVLNode<T> insert(T value, AVLNode<T> x) {
        if(x==null)x=new AVLNode<T>(value);
        else {
            //System.out.println(h(x.left)+" "+h(x.right));
            if(value.compareTo(x.val)>0) {
                x.right=insert(value,x.right);
                if(h(x.right)-h(x.left)==2) {
                    if(value.compareTo(x.right.val)>0) {
                        x=R(x);
                    }
                    else {
                        x=RL(x);
                    }
                }
                x.height=Math.max(h(x.left),h(x.right))+1;
            }
            else if(x.val.compareTo(value)>0) {
                x.left=insert(value,x.left);
                if(h(x.right)-h(x.left)==-2) {
                    if(value.compareTo(x.left.val)<0) {
                        x=L(x);
                    }
                    else {
                        x=LR(x);
                    }
                }
                x.height=Math.max(h(x.left),h(x.right))+1;
            }
            else {
                x.height = Math.max( h(x.left), h(x.right) ) + 1;
            }

        }
        return x;
    }
    public void remove(T value) {
        if(value==null)throw new NullPointerException("No Such Value");
        delete(value,root);
    }
    private AVLNode<T> delete(T value,AVLNode<T> x) {
        if(x==null)return null;
        if(value.compareTo(x.val)>0) {
            x.right=delete(value,x.right);
            if(h(x.left)-h(x.right)==2) {
                if(x.left.left!=null) {
                    x=L(x);
                }
                else {
                    x=LR(x);
                }
            }
        }
        else if(value.compareTo(x.val)<0){
            x.left=delete(value,x.left);
            if(h(x.right)-h(x.left)==2) {
                if(x.right.right!=null) {
                    x=R(x);
                }
                else {
                    x=RL(x);
                }
            }
        }
        else if(x.right!=null){
            x.val=min(x.right);
            x.right=delete(x.val,x.right);
        }
        else {
            x=x.left;
        }
        if(x!=null)
            x.height=Math.max(h(x.left),h(x.right))+1;
        return x;
    }
    private T min(AVLNode<T> x) {
        T ans;
        if(x.left!=null) {
            ans=min(x.left);
        }
        else {
            T temp=x.val;
            if(x.right!=null) {
                x=x.right;
            }
            else
                x=null;
            ans=temp;
        }
        return ans;
    }
    public AVLTree(){
        root=null;
    }
    public void print() {
        if(root==null)
            throw new NullPointerException();
        else {
            ThoughBinaryTree(root);
        }
    }
    private void ThoughBinaryTree(AVLNode<T> x) {
        if(x==null)
            return;
        else {
            System.out.print(x.val + "\t");
            ThoughBinaryTree(x.left);
            ThoughBinaryTree(x.right);
        }
    }
}
